package tulingxueyuan117;

import javax.swing.*;
import java.util.HashSet;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2022/5/22 20:45
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 */
public class p15_相交链表_160 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(8);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(1);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        listNode5.next = listNode6;
        listNode6.next = listNode7;
        listNode7.next = listNode2;

        ListNode res = getIntersectionNode(listNode, listNode5);
        System.out.println(res);
    }


    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
        val = x;
        next = null;
        }
    }

//    自己用哈希表做的
//    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        ListNode h1 = headA;
//        ListNode h2 = headB;
//        HashSet<ListNode> listNodes = new HashSet<>();
//        while (h1 != null){
//            listNodes.add(h1);
//            h1 = h1.next;
//        }
//        while (h2 != null){
//            if(listNodes.contains(h2)){
//                return h2;
//            }else {
//                h2 = h2.next;
//            }
//        }
//        return null;
//    }

//    视频中双指针
//    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if(headA == null || headB == null){
//            return null;
//        }
//        ListNode pA = headA;
//        ListNode pB = headB;
//        while (pA != pB){
//            if(pA == null){
//                pA = headB;
//            }else {
//                pA = pA.next;
//            }
//            if(pB == null){
//                pB = headA;
//            }else {
//                pB = pB.next;
//            }
//        }
//        return pA;
//    }

//    视频讲解
//    先遍历一遍长短链，然后作差，m-n=d;然后从较长的链表先移动d步，然后双指针，指到同一节点
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int L1 = 0, L2 = 0, diff = 0;
        ListNode head1 = headA, head2 = headB;
        while (head1 != null){
            L1 ++;
            head1 = head1.next;
        }
        while (head2 != null){
            L2 ++;
            head2 = head2.next;
        }
        if(L1 < L2){
            head1 = headB;
            head2 = headA;
            diff = L2 - L1;
        }else {
            head1 = headA;
            head2 = headB;
            diff = L1 - L2;
        }
        for(int i = 0; i < diff; i++) {
            head1 = head1.next;
        }
        while (head1 != null && head2 != null){
            if(head1 == head2){
                return head1;
            }else {
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        return null;
    }

}
